package HighMethod08;

import java.util.Arrays;

public class Package01 {

    public static void Print_Arr(int[][] m) {
        for (int i = 0; i < m.length; i++) {
            for (int j = 0; j < m[i].length; j++) {
                System.out.printf("%3d", m[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * 递归实现零一背包(有重复求解问题)
     * 从后往前
     *
     * @param V
     * @param W
     * @param i 当前物品的下标
     * @param n 物体个数
     * @param j 当前背包总容量，是一个变化值
     * @return
     */
    public static int Knapsack(int[] V, int[] W, int i, int n, int j) {

        if (i == n) {
            return j > W[n] ? V[n] : 0;
        } else {
            if (j < W[i]) {         //当前背包容量装不下i物品，i+1
                return Knapsack(V, W, i + 1, n, j);
            } else {              //两种情况:不装当前物品\装当前物品;
                return Math.max(Knapsack(V, W, i + 1, n, j),
                        Knapsack(V, W, i + 1, n, j - W[i]) + V[i]);
            }
        }
    }

    //递归查表 从前往后 i=1
    public static int Knapsack2(int[] V, int[] W, int i, int j, int[][] m) {

        if (i == 1) {
            m[i][j] = j > W[1] ? V[1] : 0;
        } else if (m[i][j] > 0) {
            return m[i][j];
        } else {
            if (j < W[i]) {         //当前背包容量装不下i物品，i+1
                m[i][j] = Knapsack2(V, W, i - 1, j, m);
            } else {              //两种情况:不装当前物品\装当前物品;
                m[i][j] = Math.max(Knapsack2(V, W, i - 1, j, m),
                        Knapsack2(V, W, i - 1, j - W[i], m) + V[i]);
            }
        }
        return m[i][j];
    }

    //递归查表 从后往前 i=n
    public static int KnapsackOptimized(int[] V, int[] W, int i, int n, int j, int[][] m) {

        if (i == n) {
            m[i][j] = j > W[n] ? V[n] : 0;
        } else if (m[i][j] > 0) {
            return m[i][j];
        } else {
            if (j < W[i]) {         //当前背包容量装不下i物品，i+1
                m[i][j] = KnapsackOptimized(V, W, i + 1, n, j, m);
            } else {              //两种情况:不装当前物品\装当前物品;
                m[i][j] = Math.max(KnapsackOptimized(V, W, i + 1, n, j, m),
                        KnapsackOptimized(V, W, i + 1, n, j - W[i], m) + V[i]);
            }
        }
        return m[i][j];
    }

    //非递归查表  求所放物品的价值总和的最大值
    public static int KnapsackOptimized2(int[] V, int[] W, int n, int c, int[][] m) {

        int i = 0, j = 0;
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= c; j++) {
                m[i][j] = m[i - 1][j];      //先初始化有i个物品时的最优装载为前 i-1个物品时的最优装载，然后考虑能都继续装载
                if (j >= W[i]) {            //空间允许的话，装入第i个物品并减去相应容量，否则就不装
                    m[i][j] = Math.max(m[i - 1][j], m[i - 1][j - W[i]] + V[i]); //取满足装载的最大价值
                }
            }
        }
        return m[n][c];
//        return m[i-1][j-1];
    }

    public static void main(String[] args) {
        int n = 5;   //物品个数
        int c = 10;    //容量
        int[] W = {0, 2, 2, 6, 5, 4};        //物品重量
        //          0 1 2 3 4 5
        int[] V = {0, 6, 3, 15, 4, 6};        //物品价值

//        int maxv = Knapsack(V, W, 1, n, c);
//        System.out.println("零一背包，能装物品的最大价值："+maxv);

        int[][] m = new int[6][11];

//        int maxv2 = KnapsackOptimized(V, W, 1, n, c, m);      //从后往前,穿的参数刚好相反
//        int maxv2 = Knapsack2(V, W, n, c, m);            //从前往后，穿的参数刚好相反
//        System.out.println("零一背包，能装物品的最大价值：" + maxv2);
//        Print_Arr(m);

        int max = KnapsackOptimized2(V, W, n, c, m);            //非递归查表
        System.out.println("零一背包，能装物品的最大价值：" + max);
        Print_Arr(m);

        int []X ={0,0,0,0,0,0};     //0表示没有放 1表示放入背包里了
        TraceBack(m,W,c,X);
        //回溯：再装最大价值总和的情况下，输出装入背包的物品
        for(int i =0;i<W.length;i++){
            if(X[i]==1) {
                System.out.printf("[W:%3d,V:%3d]\t", W[i],V[i]);
            }
        }
    }

    private static void TraceBack(int[][] m, int[] w, int c, int[] x) {
        int i = w.length-1;
        for(;i>1;--i){
            if(m[i][c]!=m[i-1][c]){
                x[i]=1;
                c = c-w[i];
            }
        }
        if(m[1][c]!=0){
            x[1] =1;
        }
        System.out.println(Arrays.toString(x));

    }
}
